Multi-hop networks that act in a self-organising manner are finding application in many fields such as industrial control, building automation, embedded sensing, etc. Devices in the network communicate with each other in a wireless manner, using low-power, low-cost radio. This allows more freedom in positioning the devices, since a mains connection is not required for the wireless inter-device communication.
A standard for wireless control of such networks, rapidly becoming established, is the ZigBee standard developed by the ZigBee Alliance. The ZigBee standard describes high-level communication between devices using low-power digital radios, and is based on the IEEE 802.15.4 standard, which in turn specifies the Physical (PHY) layer and the Medium Access (MAC) layer for wireless personal area networks (WPANs).
An example of a multi-hop network might be a building automation network with various types of devices such as lamps, switches, ventilators, motion sensors, etc. These devices, each of which is a network ‘node’ (i.e. is equipped with a wireless interface), can organise themselves into a network with one device acting as the coordinator, and all other devices being either ‘routers’ or ‘end devices’. A router can, in contrast to an end device, pass messages from one node to another, acting as an intermediate node. For example, a number of lamps in a room can be end-devices, controlled by a switch with router capability.
Devices or nodes in such a wireless network communicate by exchanging messages or network commands in the form of frames. The structure of a frame is laid out in the appropriate specification, for example a frame usually comprises a header and a payload, and certain fields at specific ‘locations’ in the frame can inform the recipient, among others, of the type of command being passed. Since the wireless range of the transmitters used in this type of low-power, low cost network is limited, messages can be sent from a sending device to a remote receiving device by using intermediate devices in a manner referred to as ‘multi-hop’ routing. The further away the target node is located, the greater the number of ‘hops’ that will be taken to deliver the message. Before sending a message to a destination node (also referred to as target node), a source node (also referred to as initiator node or originator node) must first establish a network path to that target or destination node, i.e. it must first discover the route to the destination node. In a multi-hop network, a source node could connect to a destination node over any number of possible routes. Obviously, a route having a small number of intermediate nodes, and therefore a small number of ‘hops’, each of them having satisfactory link quality, is preferable over a route with more hops or weaker links. A number of techniques have been developed to assist in determining an optimal route from a source node to a destination node.
Using the current standards, route discovery, performed for example using the technique of AODV (ad-hoc on-demand distance vector) routing, is a very resource consuming task. Route request commands (RREQs) are re-broadcasted by every router within the defined radius (in TCP/IP networks called time-to-live (TTL)) from the source, despite the fact that it may have reached its destination. Furthermore, techniques to increase broadcast reliability, especially used for shared-media-based communication (such as multihop wireless), further increase the number of packets resulting from a single route request. An example is the passive acknowledgement technique used in the ZigBee standard, where a router, after re-broadcasting a RREQ packet, keeps track for a given time whether all its neighbour routers have re-broadcasted it further, and if at least one has not, that router transmits the RREQ packet anew. Furthermore, on reception of the same RREQ packet over a path with a better path cost, the packet must be re-broadcast anew. Obviously, each message will also arrive at a multitude of nodes for which the message is not intended, e.g. the nodes far away from both the source and target node and not located between those nodes. The result is a considerable burst in traffic, referred to as a ‘broadcast storm’, which may—in large networks—last for several seconds. Because of the limitations in bandwidth and the high level of traffic triggered as a result of a single route discovery request, packets can collide so that requests and replies are not delivered and the request can fail. Even if the route request delivery was successful, collisions or medium occupation resulting from the broadcast storm may prevent the destination's confirmation route reply packet (usually unicasted to the source node along the discovered path) from reaching the source node, so that the route discovery ultimately fails. This may force the initiator node to repeat the whole route discovery procedure, i.e. start with another broadcast storm.
Furthermore, route discovery according to the current standards must be carried out for each source-destination pair independently, i.e. a broadcast storm is triggered each time a node requires a route to one other node. For a node that needs to establish routes to multiple other nodes, this can lead to noticeable delays between an action (e.g. throw a switch in a lighting control network) and the intended reaction (turn on all the lights controlled by this switch). Also, the high level of traffic arising from the broadcast storms not only leads to inefficiency in the route discovery process, but it can also block important application-layer commands so that these need to be issued again.
Obviously, one way to counteract these inefficiencies in route discovery would be to make each device in the network aware of its position in the network tree or mesh or its geographical position and the position(s) of the devices to which it should send its command or data packets. Obviously, such information would change each time a device is moved or replaced. Manual configuration of such position information is impracticable, especially in large networks, where these corrective measures might even need to be carried out on a daily basis, resulting in a high level of maintenance and an unacceptable cost factor. Furthermore, path data would have to be provided or special position-based routing algorithms would have to be used. On the other hand, tree routing mechanisms usually results in too long, and therefore sub-optimal and potentially overloaded routes, and there is no backup possibility if one node on the route (temporarily) fails. The tree routing mechanism implemented by ZigBee is based on the Cskip tree addressing method that limits the possible network topologies and is impracticable for larger networks. Other tree-based routing mechanisms require extensive communication and calculation effort for establishment and maintenance of the overlay tree structure. With the latter, the advantages of the self-organising wireless network—flexibility and ease of use—would effectively be cancelled out. Evidently, tree routing is not a practicable solution.
Therefore, it is an object of the invention to provide a more efficient method of performing route discovery in a multi-hop network while avoiding the problems outlined above.